//Given a string containing digits from 2-9 inclusive, return all possible 
//letter combinations that the number could represent. Return the answer in any order. 
//
//
// A mapping of digit to letters (just like on the telephone buttons) is given 
//below. Note that 1 does not map to any letters. 
//
// 
//
// 
// Example 1: 
//
// 
//Input: digits = "23"
//Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
// 
//
// Example 2: 
//
// 
//Input: digits = ""
//Output: []
// 
//
// Example 3: 
//
// 
//Input: digits = "2"
//Output: ["a","b","c"]
// 
//
// 
// Constraints: 
//
// 
// 0 <= digits.length <= 4 
// digits[i] is a digit in the range ['2', '9']. 
// 
// Related Topics Hash Table String Backtracking 👍 7944 👎 597


package leetcode.editor.en;

import com.sun.deploy.util.StringUtils;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class _17_LetterCombinationsOfAPhoneNumber {
    public static void main(String[] args) {
        Solution solution = new _17_LetterCombinationsOfAPhoneNumber().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        String[] map = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        public List<String> letterCombinations(String digits) {
            List<String> r = new ArrayList<>();
            if (digits.length()==0) {
                return r;
            }
            dfs(digits, 0, "", r);
            return r;
        }

        private void dfs(String digits, int i, String s, List<String> r) {
            if (s.length() == digits.length()) {
                r.add(s);
                return;
            }
            String key = map[digits.charAt(i) - '0'];
            for (int j = 0; j < key.length(); j++) {
                dfs(digits, i+1, s+key.charAt(j), r);
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}